Three-dimensional (“3D”) representations of information present specific challenges not found in two-dimensional (“2D”) representations, for example, in 3D representations certain elements may be occluded by the presence of other elements in the representation. Traditional approaches to dealing with occlusion avoidance in 3D representations include techniques such as cutting planes, viewer navigation, filtering of information, and transparency. While these methods provide clearer visual access to elements of interest it removes much of the contextual information from a representation.
In 2D representations all information is restricted to a plane perpendicular to a view point. The addition of the third spatial variable (or z component) allows objects to be interposed or positioned between the viewpoint and other objects in a scene, thus partially or completely hiding them from view. The preservation of spatial relationships and presentation of relationships to the occluding objects is important in constructing a physically plausible scene or in other words the detail of the scene is maintained in the context in which it exists. For example, in volumetric rendering of 3D data it is often the case that the near-continuous nature of the data makes occlusion of interior features of the data inevitable. This phenomenon is important in supporting perception of the scene as a 3D representation, but a user may very well wish to examine these hidden interior regions.
Solutions are available that provide visual access (i.e. clear lines of sight) to previously occluded elements. Several of these solutions are described by Cowperthwaite in Occlusion Resolution Operators for Three-Dimensional Detail-In-Context (Cowperthwaite, David J., Occlusion Resolution Operators for Three-Dimensional Detail-In-Context (Burnaby, British Columbia: Simon Fraser University, 2000)) which is incorporated herein by reference. Cutting planes may be used to remove information from a scene. Increasing transparency (or reducing the opacity) of objects allows more distant objects to be seen through those more proximal to the viewer. Navigation of the viewer, whether egocentric (moving the viewer within the data space) or exocentric (moving or re-orientation of the data space) may lead to a configuration where occlusion is resolved. Finally, information filtering may be used to reduce the density of data in a representation. These are all common methods of occlusion resolution and all operate by reducing the amount (or visibility) of contextual information in the final presentation. Similar methods such as panning zooming and filtering have also been traditionally applied to dealing with large or congested displays of information in two-dimensions. Thus, the removal of information from a presentation has been one approach to dealing with the large information spaces.
Another approach has been the development of “detail-in-context” presentation algorithms. The field of detail-in-context viewing is concerned with the generation of classes of information presentations where areas or items defined as focal regions or regions of interest (“ROI”) are presented with an increased level of detail, without the removal of contextual information from the original presentation. For example, regions of greatest interest may be displayed at an enlarged size, providing more visual detail, while the scale of the surrounding context may be adjusted to provide the space for the magnification of the ROI.
In the detail-in-context discourse, differentiation is often made between the terms “representation” and “presentation”. A “representation” is a formal system, or mapping, for specifying raw information or data that is stored in a computer or data processing system. For example, a digital map of a city is a representation of raw data including street names and the relative geographic location of streets and utilities. Such a representation may be displayed visually on computer screen or printed on paper. On the other hand, a presentation is a spatial organization of a given representation that is appropriate for the task at hand. Note also that the term “visualization” in computer graphics processing is often used to identify the process of applying computer graphics techniques to the problem of presenting information to users. That is, a “representation” is transformed into a “presentation” through the process of visualization. Thus, a presentation of a representation organizes such things as the point of view and the relative emphasis of different parts or regions of the representation. For example, a digital map of a city may be presented with a work route magnified to reveal street names. Thus, detail-in-context presentations allow for magnification of a particular ROI in a representation while preserving visibility of the surrounding representation. In other words, in detail-in-context presentations focal regions are presented with an increased level of detail without the removal of contextual information from the original representation. In general, a detail-in-context presentation may be considered as a distorted view (or distortion) of a portion of the original representation where the distortion is the result of the application of a “lens” like distortion function to the original representation. For reference, a detailed review of various detail-in-context presentation techniques may be found in Carpendale's A Framework for Elastic Presentation Space (Carpendale, Marianne S. T., A Framework for Elastic Presentation Space (Burnaby, British Columbia: Simon Fraser University, 1999)) which is incorporated herein by reference.
The process of generating 2D detail-in-context presentations as described by Carpendale may be encompassed by the term Elastic Presentation Space (“EPS”). EPS includes techniques that allow for the adjustment of a visual presentation without interfering with the information content of the representation. The adjective “elastic” is included in the term as it implies the capability of stretching and deformation and subsequent return to an original shape. Basically, in EPS graphics technology, a two-dimensional visual representation is placed onto a surface; this surface is placed in three-dimensional space; the surface, containing the representation, is viewed through perspective projection; and the surface is manipulated to effect the reorganization of image details. The presentation transformation is separated into two steps: surface manipulation or distortion and perspective projection. Extensions of classical 2D detail-in-context viewing algorithms to 3D by the addition of a z component do not adequately address the situation.
To reiterate, a unique situation arises with detail-in-context viewing and 3D representations of information in that the possibility of the ROI being occluded exists. As discussed above, there are a number of methods which have been developed, independent of detail-in-context viewing, for dealing with situation of occlusion in 3D information representations. Each of these methods involves removing information from a display in some manner, which is contrary to the goals of detail-in-context viewing.
Several systems are known which provide techniques for occlusion avoidance in computer graphics systems. In U.S. Pat. No. 5,999,879 (Yano), a navigation apparatus for stereoscopically displayed road maps containing shape data for buildings, mountains, and similar landmarks is disclosed. With the disclosed apparatus, when a landmark object overlaps a section of road in stereoscopic view, the shape of the overlapping landmark may be changed so that the occluded section of road may be observed. The disclosed apparatus cannot provide detail-in-context presentations. In U.S. Pat. No. 5,689,628 (Robertson), a method and system are disclosed for maintaining a view of a selected display object while navigating in an n-dimensional, workspace. As such, the disclosed method and system exemplify, at most, a viewer navigation-like approach to occlusion avoidance. Thus, none of these systems disclose a method or system for occlusion avoidance in a manner that is optimized for 3D information representations and detail-in-context viewing.
A need therefore exists for a method and system that will allow for effective occlusion avoidance and detail-in-context viewing of representations of three-dimensional data.